package 中等.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个字符串 s ，请你判断它是否 有效 。
 * 字符串 s 有效 需要满足：假设开始有一个空字符串 t = "" ，你可以执行 任意次 下述操作将 t 转换为 s ：
 * 将字符串 "abc" 插入到 t 中的任意位置。形式上，t 变为 tleft + "abc" + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能为 空 。
 * 如果字符串 s 有效，则返回 true；否则，返回 false。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions
 */
public class 检查替换后的词是否有效_1003 {

    public static void main(String[] args) {

        System.out.println(isValid("aabcbc"));

    }

    /**
     * 栈
     * 遇到 c 之后弹出栈顶 2 个字符，判断是不是 b a
     * 注意：遇到 c 时栈里面小于 2 个字符，则一定不是有效的
     */
    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (c == 'c') {
                if (stack.size() < 2) {
                    return false;
                }
                Character b = stack.pollFirst();
                Character a = stack.pollFirst();
                if (b == 'b' && a == 'a') {
                    continue;
                }

                stack.addFirst(a);
                stack.addFirst(b);
            }
            stack.addFirst(c);
        }

        return stack.size() == 0 ? true : false;
    }

}
